class RBNode{
public:
	bool color;
	RBNode* parent;
	RBNode* left;
	RBNode* right;
	int key;
	
	RBNode(const int& key): key(key), color(true), left(nullptr), right(nullptr), parent(nullptr)
	{
		
	}RBNode(): key(0), color(true), left(nullptr), right(nullptr), parent(nullptr)
	{
		
	}
};

class RBTree{
public:
	typedef RBNode* node_ptr;
	RBTree():root(nulptr){
	}
	void left_rotate(node_ptr x);
	void right_rotate(node_ptr x);
	bool getcolor(node_ptr x) const;
	node_ptr RBInsert(int key);
	node_ptr RBDelete(node_ptr z);
	node_ptr TreeMinimum(node_ptr z);
	node_ptr TreeSuccessor(node_ptr z);
	node_ptr parentof(node_ptr cur);
	node_ptr leftof(node_ptr cur);
	void setcolor(node_ptr cur, bool color);
	node_ptr rightof(node_ptr cur);
	void Search(node_ptr item);
	void PrintTree();
	~RBTree(){
		destroy(root);
	}
private:
	node_ptr root;
	static node_ptr nulptr;
	void destroy(node_ptr item);
	void Print();
	void RB_insert_fixup(node_ptr z);
	void RB_delete_fixup(node_ptr z);
	static bool RED;
	static bool BLACK;
	int _size; //record element number
};

